package _70ClimbingStairs;

public class CSolution {

  public static void main(String[] args) {
    System.out.println("aa");
    System.out.println(climbStairsOld(0));
    System.out.println(climbStairsOld(1));
    System.out.println(climbStairsOld(2));
    System.out.println(climbStairsOld(3));
    System.out.println(climbStairs(0));
    System.out.println(climbStairs(1));
    System.out.println(climbStairs(2));
    System.out.println(climbStairs(3));
  }

  private static int climbStairsOld(int n) {
    if (n <= 1) {
      return 1;
    }
    return climbStairsOld(n - 1) + climbStairsOld(n - 2);
  }

  private static int climbStairs(int n) {
    int[] ways = new int[n+1];
    ways[0] = 1;
    ways[1] = 1;
    if (n < 2) {
      return ways[n];
    }
    for (int i = 2; i < ways.length; i++) {
      ways[i] = ways[i - 1] + ways[i - 2];
      if (i == n) {
        return ways[i];
      }
    }
    return 1;
  }
}
